package com.study.homework;

public class MyLru {

    private final int maxLen;
    private int currLen;
    private Node header;

    public MyLru(int len) {
        this.maxLen = len;
    }

    public String toString() {
        Node h = header;
        StringBuilder sb = new StringBuilder();
        while (h != null) {
            sb.append(h.data)
                    .append(",");
            h = h.next;
        }

        return sb.toString();
    }


    public void put(int data) {
        Node node = findNode(data);

        if (node == null) {
            node = getNode(data);
        }

        if (header == null) {
            header = node;
            return;
        }

        node.next = header;
        header.pre = node;
        header = node;

        resize();
    }


    public int get(int data) {
        Node node = findNode(data);
        if (node == null) {
            return -1;
        }

        if (node.pre == null) {
            return node.data;
        }

        node.pre.next = node.next;
        node.next.pre = node.pre;

        node.next = header;
        node.pre = null;
        header.pre = node;
        header = node;

        resize();
        return node.data;
    }

    private void resize() {
        int l = maxLen;
        Node h = header;

        while (h != null && l > 0) {
            h = h.next;
            l--;
        }

        if (h == null) {
            return;
        }

        while (h != null) {
            h.pre.next = null;
            h.pre = null;
            h = h.next;
        }
    }

    private Node getNode(int data) {
        Node node = new Node();
        node.data = data;
        node.next = null;
        node.pre = null;
        return node;
    }

    private Node findNode(int data) {
        Node h = header;
        while (h != null && h.data != data) {
            h = h.next;
        }
        return h;
    }


    class Node {
        int data;
        Node next;
        Node pre;
    }
}
